package com.example.designpatterns.strategy.sorting;

import com.example.designpatterns.strategy.Strategy;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

/**
 * 桶排序策略 - 使用桶排序算法实现排序
 * 时间复杂度：平均O(n+k)，最坏O(n²)，其中k是桶的数量
 * 空间复杂度：O(n+k)
 * 稳定性：取决于桶内排序算法，通常为稳定
 * 适用于均匀分布的数据，不适合极端分布的数据
 */
public class BucketSortStrategy implements Strategy<int[], int[]> {
    
    // 桶的默认数量
    private static final int DEFAULT_BUCKET_COUNT = 10;
    
    @Override
    public int[] execute(int[] input) {
        if (input == null || input.length <= 1) {
            return input;
        }
        
        // 创建数组副本，不修改原始数据
        int[] array = Arrays.copyOf(input, input.length);
        int n = array.length;
        
        // 找出数组中的最大值和最小值
        int minValue = array[0];
        int maxValue = array[0];
        for (int i = 1; i < n; i++) {
            if (array[i] < minValue) {
                minValue = array[i];
            } else if (array[i] > maxValue) {
                maxValue = array[i];
            }
        }
        
        // 计算合适的桶数量，避免桶太多或太少
        int bucketCount = Math.min(DEFAULT_BUCKET_COUNT, maxValue - minValue + 1);
        
        // 计算桶的范围
        double bucketSize = (double) (maxValue - minValue + 1) / bucketCount;
        
        // 创建桶（二维动态数组）
        List<List<Integer>> buckets = new ArrayList<>(bucketCount);
        for (int i = 0; i < bucketCount; i++) {
            buckets.add(new ArrayList<>());
        }
        
        // 将元素分配到不同的桶中
        for (int i = 0; i < n; i++) {
            int bucketIndex = (int) Math.min(bucketCount - 1, 
                    (array[i] - minValue) / bucketSize);
            buckets.get(bucketIndex).add(array[i]);
        }
        
        // 对每个桶内部进行排序
        for (List<Integer> bucket : buckets) {
            Collections.sort(bucket);
        }
        
        // 将排序后的元素合并回原数组
        int index = 0;
        for (List<Integer> bucket : buckets) {
            for (int value : bucket) {
                array[index++] = value;
            }
        }
        
        return array;
    }
} 